#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

// 70. 爬楼梯
// 假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
// 每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
// 输入：n = 2
// 输出：2
// 解释：有两种方法可以爬到楼顶。
// 1. 1 阶 + 1 阶
// 2. 2 阶

// 记忆化搜索
class Solution {
private:
    vector<int> memo;

    int calcWays(int n) {
        if (n == 0 || n == 1)
            return 1;
        if(memo[n] == -1)
            memo[n] = calcWays(n - 1) + calcWays(n - 2);

        return memo[n];
    }
public:
    int climbStairs(int n) {
        assert(n > 0);
        memo = vector<int>(n + 1, -1);
        return calcWays(n);
    }
};

int main() {
    cout << Solution().climbStairs(10) << endl; // 89
    return 0;
}
